package com.zhugang.week08;

import java.util.ArrayList;
import java.util.List;

/**
 * @program algorithms
 * @description: partition
 * @author: chanzhugang
 * @create: 2022/08/19 17:33
 */
public class Partition {

    /**
     * 131 分割回文串
     *
     * @param s
     * @return
     */
    private List<List<String>> result = new ArrayList<>();

    public List<List<String>> partition(String s) {
        // s 分割成多个字串，每个字串都是回文串
        backtrack(s, 0, new ArrayList<>());
        return result;
    }


    /**
     * @param s
     * @param k    阶段(下标)
     * @param path 路径
     */
    private void backtrack(String s, int k, List<String> path) {
        if (k == s.length()) {
            result.add(new ArrayList<>(path));
            return;
        }
        // 求所有子串判断是否是回文串
        for (int end = k; end < s.length(); end++) {
            if (isPalindrome(s, k, end)) {
                path.add(s.substring(k, end + 1));

                backtrack(s, end + 1, path);
                path.remove(path.size() - 1);
            }
        }
    }

    /**
     * 判断是否是回文串， 前后双指针法
     *
     * @param s
     * @param p
     * @param r
     * @return
     */
    private boolean isPalindrome(String s, int p, int r) {
        int i = p;
        int j = r;
        while (i <= j) {
            if (s.charAt(i) != s.charAt(j)) {
                return false;
            }
            i++;
            j--;
        }
        return true;
    }

    public static void main(String[] args) {
        Partition partition = new Partition();

        List<List<String>> resut = partition.partition("aab");
        System.out.println(resut.toString());
    }
}